package org.ala.linshen.dp;


import java.util.Arrays;

/**
 *  打家劫舍
 *
 *  你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 *
 *
 * 示例 1：
 *
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *      偷窃到的最高金额 = 1 + 3 = 4 。
 * 示例 2：
 *
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *      偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 */
public class Q198 {

    public static void main(String[] args) {
        Q198 q = new Q198();
        int[] nums = {2,7,9,3,1};
        System.out.println(q.rob(nums));
    }

    public int rob(int[] nums) {
        N = nums.length;
        if (N == 1) {return nums[0];}
        if (N == 2) {return Math.max(nums[0], nums[1]);}

        return V3(nums);
    }
    protected int N;
    /**
     *  记忆搜
     *  1）dfs[i]表示第i间房能偷到的最多金额
     *  2）dfs[i] = max(dfs(i - 1), dfs(i))
     */
    protected int V1(int[] nums) {
        memo = new int[N];
        Arrays.fill(memo, -1);
        return dfs(nums,N - 1);
    }
    protected int[] memo;
    protected int dfs(int[] nums, int i) {
        if (i < 0) {return 0;}
        if (memo[i] >= 0) {return memo[i];}
        return memo[i] = Math.max(dfs(nums, i - 1), dfs(nums, i - 2) + nums[i]);
    }


    /**
     *  dp
     *  1）dp[i]表示：第i间房能偷到的最多金额
     *  2）dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
     */
    protected int V2(int[] nums) {
        int max = Integer.MIN_VALUE;

        int[] dp = new int[N];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2 ; i < N ; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }


    /**
     * 空间优化
     * 1）在dp的基础上，其实只需要前一个和前二个
     */
    protected int V3(int[] nums) {
        int p2 = nums[0], p1 = Math.max(nums[0], nums[1]);
        int max = p1;
        for (int i = 2 ; i < N ; i++) {
            int p = Math.max(p1, p2 + nums[i]);
            max = Math.max(max, p);

            p2 = p1;
            p1 = p;
        }
        return max;
    }
}
